#include <stdio.h>
#include <stdlib.h>

int main(){
    int arr[] = {8,4,1,3,2,7,5,9,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    // 先找arr数组的最大值,并创建该大小的数组，用于计数的范围
    int range = 9+1;
    int *counts = (int *)calloc(range,sizeof(int));

    // 遍历数组arr
    for(int i=0;i<n;i++){
        // 将该值计入counts
        counts[arr[i]]++;
    }

    // 累加计数数组转化为位置数组
    for(int i=1;i<range;i++){
        counts[i] += counts[i-1];
    }
    
    // 构建排序结果
    int *result_arr = (int *)malloc(n*sizeof(int));
    for(int i=n-1;i>-1;i--){  // 倒序是为了稳定排序
        result_arr[counts[arr[i]]-1] = i; // 这里存的是arr中元素的位置
        counts[arr[i]]--;
    }
    // 最后需要将位置转化

    // 计数排序会占用多余内存，不建议使用

    // 平时基本上用不到，但 算法思维很好

    
    for(int i=0;i<n;i++){printf("%d ",result_arr[i]);}

    return 0;
}